// 实现int sqrt(int x)函数，计算并返回x的平方根（只保留整数部分），其中x是非负整数
// 思路，二分查找，设k从0到x的范围内，找到小于等于x的 k的平方的最大值

function mySqrt(x) {
    let left = 0
    let right = x
    let ans = -1
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (mid * mid <= x) {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

// 时间复杂度为Ologn
// 空间复杂度为O1

console.log(mySqrt(4))